package random;

import java.util.Arrays;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * 实现strStr()
 *
 * 实现 strStr() 函数。
 * 给定一个haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
 * 如果不存在，则返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class L28_important_KMP {

    public static void main(String[] args) {
        String haystack = "a";
        String needle = "a";
        int i = strStr(haystack, needle);
        System.out.println(i);
    }

    /*
    暴力解决，先判断第一个字母是否相等，不相等下一个，相等则遍历needle字符串逐个判断

    可以使用kmp算法
     */
    public static int strStr(String haystack, String needle) {

        // 为空返回0
        if (needle.length() == 0) return 0;

        // 长度大于haystack返回-1
        if (needle.length() > haystack.length()) return -1;

        int index = 0;
        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(index) == needle.charAt(0)) {
                for (int j = 0; j < needle.length(); j++) {
                    // 判断主串剩下的长度是否已经不满足子串的长度
                    if (index + needle.length() > haystack.length()) return -1;
                    if (haystack.charAt(index + j) != needle.charAt(j)) {
                        index++;
                        break;
                    }else if (j+1 == needle.length()) {
                        if (haystack.charAt(index + j) == needle.charAt(j)) {
                            return index;
                        }
                    }
                }
            }else {
                index++;
            }
        }
        if (index == 0 || index == haystack.length()){
            return -1;
        }else {
            return index;
        }
    }

    /*
    官方答案
    方法一：子串逐一比较 - 线性时间复杂度
    最直接的方法 - 沿着字符换逐步移动滑动窗口，将窗口内的子串与 needle 字符串比较。

    方法二：双指针 - 线性时间复杂度 (其实就是暴力解决方法)
    一个方法的缺陷是会将 haystack 所有长度为 L 的子串都与 needle 字符串比较，实际上是不需要这么做的。
    首先，只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较。

     */
    public static int strStr1(String haystack, String needle) {
        int L = needle.length(), n = haystack.length();

        for (int start = 0; start < n - L + 1; ++start) {
            if (haystack.substring(start, start + L).equals(needle)) {
                return start;
            }
        }
        return -1;
    }



    /*
    KMP方法实现
     */
    public int strStrKMP(String haystack, String needle) {
        //两种特殊情况
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }
        // char 数组
        char[] hasyarr = haystack.toCharArray();
        char[] nearr = needle.toCharArray();
        //长度
        int halen = hasyarr.length;
        int nelen = nearr.length;
        //返回下标
        return kmp(hasyarr,halen,nearr,nelen);

    }
    public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
        //获取next 数组
        int[] next = next(nearr,nelen);
        int j = 0;
        for (int i = 0; i < halen; ++i) {
            //发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
            //前缀的后一位,和咱们移动模式串的含义相同
            while (j > 0 && hasyarr[i] != nearr[j]) {
                j = next[j - 1] + 1;
                //超出长度时，可以直接返回不存在
                if (nelen - j + i > halen) {
                    return -1;
                }
            }
            //如果相同就将指针同时后移一下，比较下个字符
            if (hasyarr[i] == nearr[j]) {
                ++j;
            }
            //遍历完整个模式串，返回模式串的起点下标
            if (j == nelen) {
                return i - nelen + 1;
            }
        }
        return -1;
    }
    //这一块比较难懂，不想看的同学可以忽略，了解大致含义即可，或者自己调试一下，看看运行情况
    //我会每一步都写上注释
    public  int[] next (char[] needle,int len) {
        //定义 next 数组
        int[] next = new int[len];
        // 初始化
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < len; i++) {
            //我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            //就要找 k+1前一个元素在next数组里的值,即next[k+1]
            while (k != -1 && needle[k + 1] != needle[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            //然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (needle[k+1] == needle[i]) {
                ++k;
            }
            next[i] = k;

        }
        return next;
    }


}
